<?php
/**
 * @title 44. 通配符匹配 - 递归
 * @author start2004
 */

class Solution {

    /**
     * @param String $s
     * @param String $p
     * @return Boolean
     */
    function isMatch($s, $p) {
        /**
         * @since 2020-07-05 长度
         */
        $slen = strlen($s);
        $plen = strlen($p);
        // echo "-----Match, s={$s}, p={$p}", PHP_EOL;

        /**
         * @since 2020-07-05 通配符数量
         */
        $wildcardCount = substr_count($p, "*");

        /**
         * @since 2020-07-05 通配符要匹配字符串的数量
         */
        $diff = $slen-($plen-$wildcardCount);

        /**
         * @since 2020-07-05 逐个匹配
         */
        if($diff < 0){
            /**
             * @since 2020-07-05 `*`无法匹配负数
             *
             * s=a
             * p=aa
             * diff=-1
             */
            return false;
        } elseif($diff == 0){
            /**
             * @since 2020-07-05 保证p中无`*`
             *
             * s = null
             * p = *
             * diff = 0
             */
            $p = str_replace("*",  "", $p);
            $result = self::stringMatch($s, $p);
        } elseif($wildcardCount ==0) {
            /**
             * @since 2020-07-05 字符串有差值, 但`*`数量0
             */
            return false;
        } else {
            /**
             * @since 2020-07-05 逐个字符串匹配
             */
            $result = true;
            for($i=0; $i<$slen; $i++){
                // echo "i={$i}, s[i]=", $s[$i], ", p[i]=", $p[$i], PHP_EOL;

                if($p[$i] == "*"){
                    /**
                     * @since 2020-07-05 通配符数量从0到diff循环匹配
                     */
                    $pNew = substr($p, $i+1);
                    for ($d=0; $d<=$diff; $d++){
                        $sNew = substr($s, $i+$d);
                        // echo "======, count(n)={$d}, sNew={$sNew}, pNew={$pNew}", PHP_EOL;
                        $resultNew = self::isMatch($sNew, $pNew);
                        if($resultNew){
                            return true;
                            break;
                        } else {}
                    }

                    return false;
                    break;
                } else {
                    if($p[$i] != "?" AND $p[$i] != $s[$i]){
                        return false;
                        break;
                    } else {}
                }

                // echo str_repeat(PHP_EOL, 2);
            }
        }

        /**
         * @return
         */
        return $result;
    }

    /**
     * @title `p`只含`?`的匹配
     * @author start2004
     * @since 2020-07-05 Created
     *
     * @param string $s
     * @param string $p
     */
    function stringMatch($s='', $p=''){
        /**
         * @since 2020-07-05 长度
         */
        $slen = strlen($s);
        $plen = strlen($p);

        /**
         * @since 2020-07-05 长度不一致
         */
        if($slen != $plen){
            return false;
        } else {}

        /**
         * @since 2020-07-05 逐个字符匹配
         */
        for($i=0; $i<$slen; $i++){
            if($p[$i] != "?" AND $s[$i] != $p[$i]){
                return false;
                break;
            } else {}
        }

        /**
         * @return
         */
        return true;
    }
}


/**
 * @url http://127.0.0.1/leetcode/202007/2020.07.05.php
 */
$datas = [
    ["aa", "a"],
    ["aa", "*"],
    ["cb", "?a"],
    ["adceb", "*a*b"],
    ["acdcb", "a*c?b"],
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    var_dump($data);

    $obj = new Solution();
    $result = $obj->isMatch($data[0], $data[1]);
    var_dump($result);
    echo str_repeat("<br>", 3);
}
$xhprof->end();
